package List;

/**
 * 23.合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class mergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        boolean isallnull = true;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                isallnull = false;
                break;
            }
        }
        if (isallnull) return lists[0];
        ListNode head = null;
        int min = 10001;
        int falg = 0;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null && lists[i].val < min) {
                min = lists[i].val;
                falg = i;
            }
        }
        head = lists[falg];

        if (lists[falg] != null) {
            lists[falg] = lists[falg].next;
        }

        head.next = mergeKLists(lists);
        return head;
    }


    /**
     * hot100二刷
     */
    public  ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        boolean isallnull = true;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                isallnull = false;
            }
        }
        if (isallnull) return null;
        int min = 10001;
        int index = 0;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null && lists[i].val < min) {
                min = lists[i].val;
                index = i;
            }
        }
        ListNode head = lists[index];
        lists[index] = lists[index] == null ? null : lists[index].next;
        head.next = mergeKLists2(lists);
        return head;
    }



}
